#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <time.h>
#include <omp.h>
#include <ctype.h>
#include "mpi.h"

#define WORD_SIZE 6

int  load_buffer(FILE *fp,char **buffer);
int separa_arq(char nome[]);
int  separa_arq_space(FILE *fp);
int  words_qtt(FILE *fp);
char generateChar();

void generateWord(char* word,int max);
int  generateIndex();

int countwords(char **buffer_old,int size);
int countwords5(char **buffer,int size);

void copy_buffer(char **buffer_old,int size_old,char **buffer_new,int size_new);
void copy_buffer5(char **buffer_old,int size_old,char **buffer_new,int size_new);

static int cmpstringp(const void *p1, const void *p2);
int binarysearch ( char **array, char *chave , int size);
int mybsearch(char **array,int esq,int dir,char chave[],int chunk);



int main (int argc, char **argv)
{
    FILE *fp;
    int size_buffer_palavras_old,max_palavras_old,size_buffer_palavras_new;
    char **buffer_palavras_old,**buffer_palavras_new;
    char **buffer_clean_old,**buffer_clean_new;
    int size_buffer_clean_old,size_buffer_clean_new;

    int i,taskid,ntasks;
    int offset,chunksize;
    int dest,source;
    int cont;
    double time_start,time_end,time_all_start,time_all_end;
    char **word_bigger_5;

    MPI_Status status;

    MPI_Init(&argc,&argv);

    MPI_Comm_rank(MPI_COMM_WORLD,&taskid);
    MPI_Comm_size(MPI_COMM_WORLD,&ntasks);

    time_start = MPI_Wtime();

    fp = fopen("palavras.txt","r");
    separa_arq_space(fp);
    //fclose(fp);
    fp = fopen("arquivo.txt","r");

    size_buffer_palavras_old = words_qtt(fp); /* conta as palavras para iniciar o buffer de palavras inteiras com repetiçoes */
    buffer_palavras_old = (char **)malloc(sizeof(char *) * size_buffer_palavras_old);

    max_palavras_old = load_buffer(fp,buffer_palavras_old); /* carrega o buffer e retorna a maior palavra do texto */

    //fclose(fp);

    qsort(buffer_palavras_old,size_buffer_palavras_old,
          sizeof(buffer_palavras_old[max_palavras_old]),cmpstringp); /* ordena o buffer_palavras_old(com repeticao)*/

    size_buffer_palavras_new = countwords(buffer_palavras_old,size_buffer_palavras_old);
    buffer_palavras_new = (char **)malloc(sizeof(char *) * size_buffer_palavras_new);

    copy_buffer(buffer_palavras_old,size_buffer_palavras_old,
                buffer_palavras_new,size_buffer_palavras_new);/*copia o buffer_palavra old para o buffer_palavra_new, retirando repeticoues*/
    free(buffer_palavras_old);

    separa_arq("palavras.txt");
    fp = fopen("arquivo.txt","r");

    size_buffer_clean_old = words_qtt(fp); /* tamanho do buffer_clean_old - buffer de palvras cortadas */
    rewind(fp);
    buffer_clean_old = (char **)malloc(sizeof(char *) * size_buffer_clean_old);
    for(i = 0; i < size_buffer_clean_old; i++)
    {
        buffer_clean_old[i] = (char *)malloc(sizeof(char)*6);
        fscanf(fp,"%s",buffer_clean_old[i]);
    }
    fclose(fp);
    qsort(buffer_clean_old,size_buffer_clean_old,
          sizeof(buffer_clean_old[0]),cmpstringp); /* ordena o buffer de palavras cortadas */

    size_buffer_clean_new = countwords(buffer_clean_old,size_buffer_clean_old);
    buffer_clean_new = (char **)malloc(sizeof(char*)*size_buffer_clean_new);

    copy_buffer5(buffer_clean_old,size_buffer_clean_old,
                 buffer_clean_new,size_buffer_clean_new); /* copia o buffer de palavras cortadas buffer_clean_old com repeticoes para o buffer_clean_new
                                                                    sem repetições*/
    free(buffer_clean_old);

    qsort(buffer_clean_new,size_buffer_clean_new,
          sizeof(buffer_clean_new[0]),cmpstringp); /* oredena o buffer clean new */

    if(size_buffer_clean_new%(ntasks-1)==0){
        chunksize = (int)(floor((double)(size_buffer_clean_new)/(ntasks-1)));
    }
    else
    {
        chunksize = (int)(floor((double)(size_buffer_clean_new)/(ntasks-1))) - (size_buffer_clean_new%(ntasks-1));
    }


    offset = 0;
    int *achadas;
    achadas = (int *)malloc(sizeof(int)*size_buffer_clean_new);
    for(i = 0;i<size_buffer_clean_new;i++)achadas[i] = -1;
    time_end = MPI_Wtime();
    MPI_Barrier(MPI_COMM_WORLD);

    //printf("---%d %d %d---\n",size_buffer_clean_new,offset,chunksize);
    if(taskid == 0)
    {
        printf("\nPre-Processamento %fs\n",time_end-time_start);
        time_all_start = MPI_Wtime();
        int vetor[chunksize];

        for(i = 0;i < chunksize;i++)vetor[i] = -1;
        /* envia mensagens para os nós offset e chunksize */
        #pragma omp for
        for(dest=1; dest<ntasks; dest++)
        {

            MPI_Send(&offset,1,MPI_INT,dest,1,MPI_COMM_WORLD);
            if(dest == ntasks-1){
                int final = chunksize - ( chunksize - ((chunksize*ntasks)-size_buffer_clean_new));
                //printf("\n%d\n",final);
                MPI_Send(&final,1,MPI_INT,dest,2,MPI_COMM_WORLD);

            }
            else MPI_Send(&chunksize,1,MPI_INT,dest,2,MPI_COMM_WORLD);
            offset = offset + chunksize;
        }
        /* recebe mensagens */
        #pragma omp for
        for(dest = 1; dest < ntasks; dest++)
        {
            source = dest;
            MPI_Recv(vetor,chunksize,MPI_INT,source,1,MPI_COMM_WORLD,&status);
            MPI_Recv(&offset, 1, MPI_INT, source, 2, MPI_COMM_WORLD, &status);
            for(i = 0; i<chunksize; i++)
            {
                if(vetor[i] > -1)achadas[vetor[i]] = 1;
            }
        }
        /*procura louca*/

        int c = 0;
        for(i = 0; i<size_buffer_clean_new; i++){
            if(achadas[i] == 1)c++;
        }
        int div = 0, resto = 0;
        int tam;
        int k,n;
        cont = 0;
        time_start = MPI_Wtime();
        /* procura no buffer grande as palavras achadas no buffer pequeno */
        double time_end_10;
        double time_st_10 = MPI_Wtime();
        int digito = 1;
        #pragma omp for
        for(i = 0;i < size_buffer_palavras_new;i++)
        {
            if(strlen(buffer_palavras_new[i])<=5
               && achadas[mybsearch(buffer_clean_new,0,size_buffer_clean_new,buffer_palavras_new[i],chunksize)] == 1)
            {
                cont++;

            }/* if para verificar tamanho das palavras, caso elas sejam menor igual que 5 caracteres  */
            else if(strlen(buffer_palavras_new[i]) > 5)/*verificando palavras maiores que 5*/
            {
                tam = strlen(buffer_palavras_new[i]);
                div = floor(tam/5);
                resto = tam%5;
                if(resto > 0)
                    k = div +1;
                else
                    k = div;
                word_bigger_5 = (char**) malloc(sizeof(char *)*k);
                /* divide a palavras em n palavras de 5 letras */
                if(resto > 0)
                {
                    word_bigger_5[0] = (char *)malloc(sizeof(char)*6);
                    strcpy(word_bigger_5[0],&buffer_palavras_new[i][tam-resto]);
                    n = 1;
                }
                else n=0;

                do
                {
                    div--;
                    word_bigger_5[n] = (char*)malloc(sizeof(char)*tam);
                    strcpy(word_bigger_5[n],&buffer_palavras_new[i][div*5]);
                    word_bigger_5[n][5] = '\0';
                    n++;
                }while(div>0);
                /* fim da divisao */
                n = 0;
                /* verifica se todas as palavras cortadas existe */
                while(n < k)
                {
                    if(achadas[mybsearch(buffer_clean_new,0,size_buffer_clean_new,
                                         word_bigger_5[n],chunksize)] == 1){
                         n++;
                    }
                    else break;

                }
                /* se todas as palavras existem marcar*/
                if(k == n){
                    //printf("\nN==M%s",buffer_palavras_new[i]);
                    cont++;
                    }
            }
            if(((cont*100)/size_buffer_palavras_new) >= (10*digito) )
            {
                time_end_10 = MPI_Wtime();
                time_end_10 = time_end_10 - time_st_10;
                printf("\n%d %% das palavras em tempo: %fs\n",(10*digito),time_end_10);
                digito++;
            }

        }
            time_end = MPI_Wtime();
            time_all_end = MPI_Wtime();
            printf("\nACHADAS: %f%%\nTempo Total:%f \nTempo de busca das palavra:%f\n",
                   ((double)cont/(double)size_buffer_palavras_new)*100,
                   time_all_end-time_all_start,time_end-time_start);
       /* free(achadas);
        free(buffer_clean_new);
        free(buffer_palavras_new);*/

    }
    else
    {
        double time_start_here = MPI_Wtime();
        int off,chunk;
        MPI_Recv(&off, 1, MPI_INT, 0, 1, MPI_COMM_WORLD, &status);
        MPI_Recv(&chunk, 1, MPI_INT, 0, 2, MPI_COMM_WORLD,&status);
        int j,i = 0;
        char pal[6];
        int vet[chunk];
        for(j=0; j<chunk; j++) vet[j]=-1;
        int pct=0;
        int cont=0;
        int sum = 0;
        srand48((unsigned)(time(NULL))+offset);
        i = 0;
        //printf("\n  AQUI:MEIO%d %d %d",taskid,off,chunk);/*
        while(pct < 99)
        {

            generateWord(pal,generateIndex());
            j = mybsearch(buffer_clean_new,off,(off+chunk),pal,chunk); /* busca binaria que retorna o local da palavra */

            if(j > -1)
            {
                if(cont == 0)
                {
                    vet[cont] = j;
                    cont++;
                    sum++;
                }
                else
                {
                    for(i = 0; i < cont;i++)
                    {
                        if(vet[i] == j) break;
                    }
                    if(i == cont)
                    {
                        vet[cont] = j;
                        cont++;
                        sum++;
                    }
                }

            }

            pct = ((sum*100)/chunk);
        }
        double time_end_here = MPI_Wtime();
        time_end_here = time_end_here - time_start_here;

        MPI_Send(&vet[0],chunk,MPI_INT,0,1,MPI_COMM_WORLD);
        MPI_Send(&off,1,MPI_INT,0,2,MPI_COMM_WORLD);
        printf("\nTempo %f  no:%d\n",time_end_here,taskid);
        //printf("\n----enviei-----");
    }

    MPI_Finalize();
    free(achadas);
    free(buffer_clean_new);
    free(buffer_palavras_new);
    return 0;
}
/* conta palavras sem repeticao */
int words_qtt(FILE *fp)
{

    rewind(fp);
    char *c;
    c = (char *)malloc(sizeof(char)*50);
    int count = 0;
    while(fscanf(fp,"%s",c)!=EOF)
    {
        count++;
    }
    free(c);
    rewind(fp);
    return count;
}
/*carrega o buffer*/
int load_buffer(FILE *fp,char **buffer)
{
    char *pal;
    pal = (char *)malloc(sizeof(char)*50);
    int max = 0;
    int size;
    int i = 0;
    rewind(fp);
    while(fscanf(fp,"%s",pal)!=EOF)
    {
        size = strlen(pal)+1;
        buffer[i] = (char *)malloc(sizeof(char )*size);
        strcpy(buffer[i],pal);
        i++;
        if(size > max ) max = size;
    }
    free(pal);
    return max;
}
/* separa o arquivo */
int separa_arq(char nome[])
{
    FILE *fpt = NULL;
    FILE *ftk = NULL;
    int cont = 0;
    char c;

    fpt = fopen(nome,"r");
    ftk = fopen("arquivo.txt","w");

    while(!feof(fpt))
    {
        c = fgetc(fpt);
        if(isalpha(c) || isspace(c))/*consideramos apenas letras nos arquivos - se for alfabetico ou espaço é colocado em UPPER CASE*/
        {
            cont++;
            fputc(tolower(c),ftk);
            if(cont == 5)
            {
                fputc(' ',ftk);
                cont = 0;
            }
            else if(isspace(c))
            {
                fputc(tolower(c),ftk);
                cont = 0;
            }
        }
        else
        {
            fputc(' ',ftk);
            cont = 0;
        }
    }
    fclose(ftk);
    fclose(fpt);
    return 0;
}
/* separa o arquivo em espacos */
int separa_arq_space(FILE *fp)
{

    FILE *ftk = NULL;
    char c;
    ftk = fopen("arquivo.txt","w");

    while(!feof(fp))
    {
        c = fgetc(fp);
        if(isalpha(c) || isspace(c))
        {
            fputc(tolower(c),ftk);
        }
        else fputc(tolower(' '),ftk);
    }
    return 0;
}
/* usado no qsort() retirado de http://linux.die.net/man/3/qsort */
static int cmpstringp(const void *p1, const void *p2)
{
    /* The actual arguments to this function are "pointers to
       pointers to char", but strcmp(3) arguments are "pointers
       to char", hence the following cast plus dereference */

    return strcmp(* (char * const *) p1, * (char * const *) p2);
}
/* conta palavras sem repeticoes*/
int countwords(char **buffer_old,int size)
{
    int count = 0;
    int k;
    char pal[50];
    for(k = 0; k < size-1; ++k)
    {
        strcpy(pal,buffer_old[k]);
        count++;
        while(strcmp(pal,buffer_old[k])==0 && k < size-1)
        {
            k++;
        }
    }
    return count;
}
/* conta palavras dividindo as em 5 */
int countwords5(char **buffer,int size)
{
    int count = 0;
    int i;
    int tam;
    for(i = 0; i<size; i++)
    {
        tam = strlen(buffer[i]);
        if((tam%5) == 0) tam = tam/5;
        else tam = (tam/5) + 1;
        count += tam;
    }
    return count;
}
/* copia o buffer old para o new sem repeticoes */
void copy_buffer(char **buffer_old,int size_old,char **buffer_new,int size_new)
{
    int count = 0;
    int k,size;

    for(k = 0; k < size_old; ++k)
    {
        size = strlen(buffer_old[k])+1;
        buffer_new[count] = (char *)malloc(sizeof(char)*size);
        strcpy(buffer_new[count],buffer_old[k]);
        while(strcmp(buffer_new[count],buffer_old[k])==0 && k < size_old)
        {
            k++;
        }
        count++;
    }
}
/* copia o buffer de 5 sem repeticoes */
void copy_buffer5(char **buffer_old,int size_old,char **buffer_new,int size_new)
{
    int count = 0;
    int k;

    for(k = 0; k < size_old-1; ++k)
    {
        buffer_new[count] = (char *)malloc(sizeof(char)*6);
        strcpy(buffer_new[count],buffer_old[k]);
        while(strcmp(buffer_new[count],buffer_old[k])==0 && k < size_old-1)
        {
            k++;
        }
        count++;
    }
}
/* gera o char */
char generateChar()
{
    return (rand()%26) + 97; //Gera um número de 0 à 26 e então soma 97 para ficar de 97 à 122 que são os valores de a à z (minúsculos)
}
/* gera o tamanho das palavras */
int generateIndex()
{
    return ((rand()%5)+1);
}
/* gera a palavra */
void generateWord(char* word,int max) //Gera uma palavra de 5 characteres randômicos
{
    int i;
    for(i = 0; i < max; i++)
        word[i] = generateChar();

    word[max] = '\0';
}


/* pesquisa binaria baseada em : http://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria */
int mybsearch(char **array,int esq,int dir,char chave[],int chunk)
{
    int eesq = esq;
    int ddir = dir -1;
    dir = dir -1;
    int meio;
    while((esq <= dir) && (esq >= eesq) && (dir <= ddir))
    {
        meio = esq + ((dir-esq)/2);
        if(strcmp(array[meio],chave)==0)
        {
            return meio;
        }

        else if(strcmp(chave,array[meio])<0)
            dir = meio - 1;
        else
            esq = meio + 1;
    }
    return -1;
}

